package main

import (
	"fmt"
)

func main() {
	h := NewLeftHeap("3")
	h = Insert("1", h)
	h = Insert("5", h)
	h = Insert("2", h)
	h = Insert("4", h)

	PrintTN(h)

	h, data := DeleteMin(h)
	fmt.Println("min:", data)

	h, data = DeleteMin(h)
	fmt.Println("min:", data)
}

type TreeNode struct {
	element interface{} //数据
	left    *TreeNode   // 左右节点
	right   *TreeNode
	npl     int // 级别
}

type TN *TreeNode

func PrintTN(t TN) {
	if t == nil {
		return
	}

	PrintTN(t.left)
	PrintTN(t.right)
	fmt.Println(t.element, "")
}

func NewLeftHeap(data interface{}) TN {
	head := new(TreeNode)
	head.element = data
	head.left = nil
	head.right = nil
	head.npl = 0

	return TN(head)
}

// 插入
func Insert(data interface{}, t TN) TN {
	insertData := new(TreeNode)
	insertData.element = data
	insertData.left = nil
	insertData.right = nil
	insertData.npl = 0

	tn := merge(insertData, t)

	return tn
}

//确保有序
func merge(tn1, tn2 TN) TN {
	if tn1 == nil {
		return tn2
	}

	if tn2 == nil {
		return tn1
	}

	// fmt.Println(tn1.element, "==", tn2.element)

	if tn1.element.(string) < tn2.element.(string) {
		return MergeSort(tn1, tn2)
	} else {
		return MergeSort(tn2, tn1)
	}

}

func MergeSort(tn1, tn2 TN) TN {
	if tn1.left == nil {
		tn1.left = tn2

	} else {
		tn1.right = merge(tn1.right, tn2)

		if tn1.left.npl < tn1.right.npl {
			tn1.left, tn1.right = tn1.right, tn1.left
		}

		tn1.npl = tn1.right.npl + 1
	}
	return tn1
}

func DeleteMin(tn TN) (TN, interface{}) {
	if tn == nil {
		return nil, nil
	} else {
		leftNode := tn.left
		rightNode := tn.right
		data := tn.element

		return merge(leftNode, rightNode), data
	}
}
